mex

Time Limit: 20 Sec Memory Limit: 128 MB

Description

有一个长度为n的数组{a1,a2,…,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。

Input

第一行n,m。
　第二行为n个数。
　从第三行开始，每行一个询问l,r。

Output

一行一个数，表示每个询问的答案。

Sample Input

5 5
　2 1 0 2 1
　3 3
　2 3
　2 4
　1 2
　3 5

Sample Output

1
　2
　3
　0
　3

HINT

1<=n,m<=200000, 0<=ai<=1e9

Solution

首先，权值>n的显然是没有用的，最多排满1~n。然后我们直接使用莫队，对权值分块，查询的时候看一下这个块里面权值数是否满了，即可做到O(sqrt(n))的查询。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 200005;
const int INF = 2147483640;

int n,m,Q,num;
int a[ONE],block[ONE];
int Ans[ONE];
int C[ONE],Bc[ONE];

struct power
{
    int id;
    int l,r;
}oper[ONE];

int cmp(const power &a,const power &b)
{
    if(block[a.l] != block[b.l]) return block[a.l] < block[b.l];
    return a.r < b.r;
}

int get()
{
    int res=1,Q=1;  char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

void increa(int x) {if(x>n) return; C[x]++; if(C[x]==1) Bc[block[x]]++;}
void reduce(int x) {if(x>n) return; C[x]--; if(C[x]==0) Bc[block[x]]--;}

int Query()
{
    int pos = 1;
    for(int i=1;i<=num;i++)
        if(Bc[i] < Q) {pos = i; break;}
    for(int i=(pos-1)*Q+1;i<=n+1;i++)
        if(!C[i])
            return i-1;
}

int main()
{
    n=get();    m=get();
    Q = sqrt(n);    num = (n-1)/Q+1;
    for(int i=1;i<=n;i++)
        a[i] = get()+1, block[i] = (i-1)/Q+1;
    for(int i=1;i<=m;i++)
    {
        oper[i].id = i;
        oper[i].l = get();    oper[i].r = get();
    }

    sort(oper+1, oper+m+1, cmp);

    int l = 1, r = 0;
    for(int i=1;i<=m;i++)
    {
        while(r < oper[i].r) increa(a[++r]);
        while(oper[i].l < l) increa(a[--l]);
        while(r > oper[i].r) reduce(a[r--]);
        while(oper[i].l > l) reduce(a[l++]);
        Ans[oper[i].id] = Query();
    }

    for(int i=1;i<=m;i++)
        printf("%d\n", Ans[i]);
}